# class Solution(object):
#     def backspaceCompare(self, s, t):
#         """
#         :type s: str
#         :type t: str
#         :rtype: bool
#         """
#         st = []
#         for c in s:
#             if c == '#':
#                 if st:
#                     st.pop()
#             else:
#                 st.append(c)
#         ct = []
#         for c in t:
#             if c == '#':
#                 if ct:
#                     ct.pop()
#             else:
#                 ct.append(c)
#         return ct == st


class Solution(object):
    def backspaceCompare(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        n1 = len(s)
        n2 = len(t)
        index1 = n1 - 1
        index2 = n2 - 1
        while index1 >= 0 and index2 >= 0:
            count1 = 0
            while index1 >= 0 and (s[index1] == '#' or count1 > 0):
                if s[index1] == '#':
                    count1 += 1
                else:
                    count1 -= 1
                index1 -= 1
            count2 = 0
            while index2 >= 0 and (t[index2] == '#' or count2 > 0):
                if t[index2] == '#':
                    count2 += 1
                else:
                    count2 -= 1
                index2 -= 1
            if index1 < 0:
                if index2 < 0:
                    return True
                else:
                    return False
            else:
                if index2 < 0:
                    return False
                else:
                    if s[index1] != t[index2]:
                        return False
                    else:
                        index1 -= 1
                        index2 -= 1
        if index1 < 0 and index2 < 0:
            return True
        else:
            count1 = 0
            while index1 >= 0 and (s[index1] == '#' or count1 > 0):
                if s[index1] == '#':
                    count1 += 1
                else:
                    count1 -= 1
                index1 -= 1
            count2 = 0
            while index2 >= 0 and (t[index2] == '#' or count2 > 0):
                if t[index2] == '#':
                    count2 += 1
                else:
                    count2 -= 1
                index2 -=1
            if index1 >= 0 or index2 >= 0:
                return False
            else:
                return True

data = Solution()
# s = "ab#c"
# t = "ad#c"
# print(data.backspaceCompare(s, t))
s = "xywrrmp"
t = "xywrrmu#p"
print(data.backspaceCompare(s, t))

